﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practicum_2
{
    public class DecisionTree
    {
        public List<DataPoint> data;//all data points left in this tree;
        public DecisionTree leftChild;
        public DecisionTree rightChild;
        public Split split;
        public int classLabel;

        public DecisionTree(List<DataPoint> d)
        {
            this.data = d;
            this.leftChild = null;
            this.rightChild = null;
            this.split = null;
        }

        public double getGiniIndex()
        {
            if (this.leftChild == null)
            {//In the case of no kids
                //GiniIndex = #class1/total * #class2/total
                double class0Count = 0.0, class1Count = 0.0;
                int cl = -1;
                for (int i = 0; i < data.Count; i++)
                {
                    cl = this.data[i].classLabel;
                    if (cl == 0)
                        class0Count += 1.0;
                    else
                        class1Count += 1.0;
                }
                return (class0Count / data.Count) *
                    (class1Count / data.Count);
            }
            else
            {
                //GiniIndex = p(left)*gini(left)+p(right)*gini(right)
                double giniLeft = this.leftChild.getGiniIndex();
                double giniRight = this.rightChild.getGiniIndex();
                giniLeft *=
                    (double)this.leftChild.data.Count /
                     (double)this.data.Count;
                giniRight *=
                    (double)this.rightChild.data.Count /
                     (double)this.data.Count;
                return giniLeft + giniRight;
            }
        }

        public double getGiniIndex(double c0, double c1)
        {
            return c0 / (c0 + c1) * c1 / (c0 + c1);
        }

        public double getGiniIndex(double r0, double r1,
                double l0, double l1)
        {
            double total = r0 + r1 + l0 + l1;
            double totalLeft = l0 + l1;
            double totalRight = r0 + r1;
            return totalLeft / total * this.getGiniIndex(l0, l1) +
                totalRight / total * this.getGiniIndex(r0, r1);
        }

        public Split bestSplitForAtrribute(int attribute)
        {
            //Very inefficient method, writing an alternative 
            //might be nice.
            Split result = null;
            double[] valuesAttribute = new double[this.data.Count];
            for (int i = 0; i < data.Count; i++)
            {
                valuesAttribute[i] = data[i].attributes[attribute];
            }
            Array.Sort(valuesAttribute);
            for (int i = 1; i < data.Count; i++)
            {
                if (valuesAttribute[i] != valuesAttribute[i - 1])
                {
                    double candidateSplit =
                       (valuesAttribute[i] + valuesAttribute[i - 1]) / 2.0;
                    double cntLeft0 = 0.0, cntLeft1 = 0.0;
                    double cntRight0 = 0.0, cntRight1 = 0.0;
                    for (int j = 0; j < data.Count; j++)
                    {
                        double a = data[j].attributes[attribute];
                        int c = data[j].classLabel;
                        if (a <= candidateSplit)
                        {
                            if (c == 0)
                            {
                                cntLeft0 ++;
                            }
                            else
                            {
                                cntLeft1 ++;
                            }
                        }
                        else
                        {
                            if (c == 0)
                            {
                                cntRight0 ++;
                            }
                            else
                            {
                                cntRight1 ++;
                            }
                        }
                    }
                    double giniIndexCandidate =
                        this.getGiniIndex(cntRight0, cntRight1,
                                cntLeft0, cntLeft1);
                    Split candidate = new Split(attribute,
                            candidateSplit, giniIndexCandidate);
                    if (result == null)
                    {
                        result = candidate;
                    }
                    else
                    {
                        if (result.giniIndex > candidate.giniIndex)
                        {
                            result = candidate;
                        }
                    }
                }
            }
            return result;
        }

        public Split bestSplitAvailable()
        {
            Split result = null;
            int noOfAttributes = data[0].noOfAttributes;
            for (int i = 0; i < noOfAttributes; i++)
            {
                Split candidate = this.bestSplitForAtrribute(i);
                if (result == null)
                {
                    result = candidate;
                    //System.out.println(candidate);
                }
                else
                {
                    if (candidate != null)
                    {
                        //Console.WriteLine(candidate);
                        if (result.giniIndex > candidate.giniIndex)
                        {
                            result = candidate;
                        }
                    }
                    else
                    {
                        //Console.WriteLine("no split for attribute "+i);
                    }
                }
            }
            return result;
        }

        public void executeSplit(Split s, bool learning)
        {
            this.split = s;
            List<DataPoint> leftData = new List<DataPoint>();
            List<DataPoint> rightData = new List<DataPoint>();

            foreach (DataPoint dp in data)
            {
                if (dp.attributes[s.attributeNoSplit] < s.valueSplit)
                {
                    leftData.Add(dp);
                }
                else
                {
                    rightData.Add(dp);
                }
            }
            if (learning)
            {
                int cll1 = 0;
                int cll0 = 0;
                int clr1 = 0;
                int clr0 = 0;

                for (int i = 0; i < leftData.Count; i++)
                {
                    if (leftData[i].classLabel == 0) cll0++;
                    if (leftData[i].classLabel == 1) cll1++;
                }
                for (int i = 0; i < rightData.Count; i++)
                {
                    if (rightData[i].classLabel == 0) clr0++;
                    if (rightData[i].classLabel == 1) clr1++;
                }

                this.leftChild = new DecisionTree(leftData);
                this.rightChild = new DecisionTree(rightData);

                if (cll1 != 0 && clr1 != 0)
                {
                    if (cll0 / cll1 > clr0 / clr1)
                    {
                        leftChild.classLabel = 1;
                        rightChild.classLabel = 0;
                    }
                    else
                    {
                        leftChild.classLabel = 0;
                        rightChild.classLabel = 1;
                    }
                }
                else if (cll1 == 0)
                {
                    leftChild.classLabel = 0;
                    rightChild.classLabel = 1;
                }
                else if (clr1 == 0)
                {
                    leftChild.classLabel = 1;
                    rightChild.classLabel = 0;
                }
            }
        }

        public void partitionRecursively(int minDataPoints)
        {
            //minDataPoints is a stop condition, if there are
            //too little data points, we want to stop. Why?
            if (this.data.Count > minDataPoints)
            {
                double giniNow = this.getGiniIndex();
                Split s = this.bestSplitAvailable();
                if (s != null)
                {
                    if (s.giniIndex < giniNow)
                    {
                        //Console.WriteLine(s.giniIndex);
                        this.executeSplit(s, true);
                        leftChild.partitionRecursively(minDataPoints);
                        rightChild.partitionRecursively(minDataPoints);
                    }
                }
            }
        }

        public int getClassLabel(DataPoint pixel)
        {
            int i = 0;
            if (leftChild == null)
            {
                return classLabel;
            }

            if (pixel.attributes[split.attributeNoSplit] > split.valueSplit)
            {
                return rightChild.getClassLabel(pixel);
            }
            else
            {
                return leftChild.getClassLabel(pixel);
            }
        }
    }
}
